﻿// 1007train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <numeric>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

/*
 示例1：
输入
4
3 2 6 3
0 1 1 0
2
输出
6
说明
货物1和货物4为干货，由2辆干货中转车中转，每辆车运输一个货物，限载为3
货物2和货物3为湿货，由2辆湿货中转车中转，每辆车运输一个货物，限载为6
这样中转车统一限载货物数可以设置为6（干货车和湿货车限载最大值），是最小的取值

length
goods
types
k
 */
class Solution01
{
public:
    bool checkVerify(vector<int>& weight_v, int limit)
    {
        vector<int>box_v(car_count_, limit);

        int v_size = weight_v.size();
        for (int i=0; i<v_size; i++)
        {
            bool is_find = false;
            int curr = weight_v[i];
            for (auto&box_w:box_v)
            {
                if (box_w>=curr)
                {
                    box_w -= curr;
                    is_find = true;
                    break;
                }
            }
            if (!is_find) return false;

        }
        return true;
	    //
    }

    int getMinW(vector<int>& weight_v)
    {
        sort(weight_v.rbegin(), weight_v.rend());
        int max_num = *max_element(weight_v.begin(), weight_v.end());
        int sum = accumulate(weight_v.begin(), weight_v.end(), 0);

        int left = max_num, right = sum + 1;

        int result = 0;
        while (left<right)
        {
            int mid = left + (right - left) / 2;

            if (checkVerify(weight_v, mid))
            {
	            //调小容量
                result = mid;
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
	        //
        }
        return result;
	    //
    }

    Solution01(vector<int>&weight_v, vector<int>&kind_v, int K)
    {
        car_count_ = K;
        vector<int>dry_v;
        vector<int>wet_v;

        int v_size = weight_v.size();
        for (int i=0; i<v_size; i++)
        {
            //0代表干货，1代表湿货
	        if (kind_v[i]==0)
	        {
                dry_v.push_back(weight_v[i]);
	        }
            else
            {
                wet_v.push_back(weight_v[i]);
            }
        }
        int dry_limit, wet_limit;

        if (!dry_v.empty())
        {
            dry_limit = getMinW(dry_v);
        }
        if (!wet_v.empty())
        {
            wet_limit = getMinW(wet_v);
        }

        int result = max(dry_limit, wet_limit);
        cout << result;
	    //solu
    }
private:
    int car_count_ = 0;
};


/*
 五张牌，每张牌由牌大小和花色组成，牌大小2~10、J、Q、K、A，牌花色为红桃、黑桃、梅花、方块四种花色之一。
判断牌型:
牌型1，同花顺：同一花色的顺子，如红桃2红桃3红桃4红桃5红桃6。
牌型2，四条：四张相同数字 + 单张，如红桃A黑桃A梅花A方块A + 黑桃K。
牌型3，葫芦：三张相同数字 + 一对，如红桃5黑桃5梅花5 + 方块9梅花9。
牌型4，同花：同一花色，如方块3方块7方块10方块J方块Q。
牌型5，顺子：花色不一样的顺子，如红桃2黑桃3红桃4红桃5方块6。
牌型6，三条：三张相同+两张单。
说明：
（1）五张牌里不会出现牌大小和花色完全相同的牌。
（2）编号小的牌型较大，如同花顺比四条大，依次类推。
（3）包含A的合法的顺子只有10 J Q K A和A 2 3 4 5;类似K A 2 3 4的序列不认为是顺子

输入描述
输入由5行组成，每行为一张牌大小和花色，牌大小为2~10、J、Q、K、A，
花色分别用字符H、S、C、D表示红桃、黑桃、梅花、方块。

输出描述
输出牌型序号，5张牌符合多种牌型时，取最大的牌型序号输出

输入
4 H
5 S
6 C
7 D
8 D
输出
5
4 5 6 7 8构成顺子，输出5

A S
2 S
3 S
4 S
5 S
 */
class Solution02
{
public:
    string translateCard(string&str)
    {
        //J11 Q12 K13  
        if (str == "J") return "11";
        if (str == "11") return "J";

        if (str == "Q") return "12";
        if (str == "12") return "Q";

        if (str == "K") return "13";
        if (str == "13") return "K";

        return str;
    }

    bool checkConstrain(vector<int>&num_vec)
    {
        sort(num_vec.begin(), num_vec.end());

        int prev = num_vec[0];
        int v_size = num_vec.size();
        for (int i=1; i<v_size; i++)
        {
            if (num_vec[i] != prev + 1) return false;
            prev = num_vec[i];
        }
        return true;
	    //
    }

    bool checkSame(vector<pair<string, string>>& card_v)
    {
        string color0 = card_v[0].second;
        for (auto&item:card_v)
        {
            if (item.second != color0)
            {
                return false;
            }
        }
        return true;
    }

    int check51(vector<pair<string, string>>& card_v)
    {
        //A的合法的顺子只有10 J Q K A和A 2 3 4 5
        vector<int>real_vec;
        vector<int>a_vec;
        bool is_A = false;

        for (auto&item:card_v)
        {
	        if (item.first=="A")
	        {
                is_A = true;
                a_vec = real_vec;
                real_vec.push_back(14);
                a_vec.push_back(1);
                continue;
	        }
            string num_str = translateCard(item.first);
            real_vec.push_back(stoi(num_str));
            if (is_A)
            {
                a_vec.push_back(stoi(num_str));
            }
            //for---
        }

        bool is_real = checkConstrain(real_vec);
        if (is_A)
        {
            bool is_a = checkConstrain(a_vec);
            is_real = is_real || is_a;
        }

        bool is_same = checkSame(card_v);
        if (!is_real) return -1;
        if (is_same) return 1;
        return 5;
	    //
    }

    int check6()
    {
        //三条：三张相同+两张单
        //找3张相同
        if (num_map.size() != 3) return -1;
        for (auto&item: num_map)
        {
	        if (item.second==3)
	        {
                return 6;//牌型6
	        }
        }
        return -1;

        //check6
    }

    int check2()
    {
	    //四张相同数字 + 单张
        if (num_map.size() != 2) return -1;
        for (auto& item : num_map)
        {
            if (item.second == 4)
            {
                return 2;//牌型2
            }
        }
        return -1;
    }

    int check3()
    {
	    //三张相同数字 + 一对
        if (num_map.size() != 2) return -1;
        for (auto& item : num_map)
        {
            if (item.second == 3)
            {
                return 3;//牌型3
            }
        }
        return -1;

    }

    int check4(vector<pair<string, string>>& card_v)
    {
        if (checkSame(card_v)) return 4;
        return -1;
    }

    Solution02(vector<pair<string, string>>& card_v)
    {
/*
牌型1，同花顺：同一花色的顺子，如红桃2红桃3红桃4红桃5红桃6。
牌型2，四条：四张相同数字 + 单张，如红桃A黑桃A梅花A方块A + 黑桃K。
牌型3，葫芦：三张相同数字 + 一对，如红桃5黑桃5梅花5 + 方块9梅花9。
牌型4，同花：同一花色，如方块3方块7方块10方块J方块Q。
牌型5，顺子：花色不一样的顺子，如红桃2黑桃3红桃4红桃5方块6。
牌型6，三条：三张相同+两张单。
*/
        for (auto& card : card_v)
        {
            num_map[card.first] += 1;
        }
        int result = -1;
        
        int curr_res = check6();
        result = max(result, curr_res);

        curr_res = check51(card_v);
        result = max(result, curr_res);

        curr_res = check4(card_v);
        if (result!=1)
        {
            result = max(result, curr_res);
        }

        curr_res = check3();
        result = max(result, curr_res);

        curr_res = check2();
        result = max(result, curr_res);

        cout << result;

	    //solu
    }
private:
    unordered_map<string, int>num_map;
};


/*
牌面由颜色和数字组成，颜色为红、黄、蓝、绿中的一种，数字为0-10 中的一个
手牌颜色或者数字相同的手牌，他可以继续将该手牌打出

输入描述
输入为两行，第一行是每张手牌的数字，数字由空格分隔，第二张为对应的每张手牌的颜色，
用r y b g这4个字母分别代表4种颜色，字母也由空格分隔。手牌数量不超过10。

输出描述
输出一个数字，即最多能打出的手牌的数量。

输入
1 4 3 4 5
r y b b r
输出
3
如果打出1r，那么下面只能再打出5r，共打出两张牌，
而按照4y-4b-3b的顺序则可以打出三张牌，故输出3
 */
class Solution03
{
public:
    void backTrack(
        vector<pair<int, char>>& card_v,
        vector<bool>&checked
    )
    {
        if (track_v.size()>result.size())
        {
            result = track_v;
        }

        int v_size = card_v.size();
        for (int i=0; i<v_size; i++)
        {
            if (checked[i]) continue;

            pair<int, char>curr = card_v[i];
            bool is_available = false;
            if (track_v.empty())
            {
                is_available = true;
            }
            else
            {
                pair<int, char>prev = track_v.back();
                is_available = prev.first == curr.first || prev.second == curr.second;
            }
            
            if (is_available)
            {
                checked[i] = true;
                track_v.push_back(curr);
                backTrack(card_v, checked);
                checked[i] = false;
                track_v.pop_back();
            }
        }

	    //
    }
    Solution03(vector<pair<int,char>>&card_v)
    {
        //子集
        int v_size = card_v.size();
        vector<bool>checked(v_size, false);
        backTrack(card_v, checked);

        cout << result.size();
	    //Solu
    }
private:
    vector<pair<int, char>>track_v;
    vector<pair<int, char>>result;
};


/*
小王是一名基站维护工程师，负责某区域的基站维护
某地方有 n 个基站，1 < n < 10，已知各基站之间的距离 s，0 < s < 500 
并且基站 x 到基站 y 的距离，与基站 y 到 基站 x 的距离并不一定会相同
小王从基站 0 出发，途经每个基站 1 次，然后返回基站 0 
需要请你为他选择一条距离最短的路

输入
站点数 n 和各站点之间的距离，均为整数
3     // 表示站点数
0 2 1 // 表示站点0到各站点的路程
1 0 2 // 表示站点1到各站点的路程
2 1 0 // 表示站点2到各站点的路程
输出描述
最短路程的数值

输入
3
0 2 1
1 0 2
2 1 0
输出
3
路线为0 -> 2 -> 1 -> 0，距离为所有路线最小 1 + 1 + 1 = 3
如果选择路线0 -> 1 -> 2 -> 0，距离为 2 + 2 + 2 = 6
 */

class Solution04
{
public:
    int computeTask(vector<vector<int>>& grid)
    {
        if (track_v.empty()) return 0;
        int track_size = track_v.size();
        int cost = 0;
        for (int i=0; i<track_size-1; i++)
        {
            int row = track_v[i];
            int col = track_v[i + 1];
            cost += grid[row][col];
        }

        cost += grid[0][track_v[0]];

        if (track_size==total_)
        {
            cost += grid[track_v.back()][0];
        }
        return cost;
	    //
    }

    void backTrack(
        vector<vector<int>>& grid,
        vector<bool>&checked
    )
    {
        int track_cost = computeTask(grid);
        if (track_cost > min_cost) return;

        if (track_v.size()==total_)
        {
            min_cost = min(min_cost, track_cost);
            return;
        }
        
        for (int i=1; i<=total_; i++)
        {
            if (checked[i]) continue;
            checked[i] = true;
            track_v.push_back(i);
            backTrack(grid, checked);
            checked[i] = false;
            track_v.pop_back();
            //for---
        }

        //
    }
    Solution04(int total, vector<vector<int>>&grid)
    {
        total_ = total-1;
        vector<bool>checked(total, false);
        backTrack(grid, checked);

        cout << min_cost;
        return;
        //
    }
private:
    int min_cost = INT_MAX;
    vector<int>track_v;
    int total_ = 0;
};

vector<string>handleInput(string&str)
{
    vector<string>res;
    stringstream oh_sstream(str);
    string token;
    while (oh_sstream>>token)
    {
        res.push_back(token);
    }
    return res;
}

int main()
{
	{
        int total;
        cin >> total;

        vector<vector<int>>grid(total, vector<int>(total));

        for (int r=0; r<total; r++)
        {
	        for (int c=0; c<total; c++)
	        {
                cin >> grid[r][c];
	        }
        }

        Solution04 solu(total, grid);

        return 0;
	}
	{
        string num_input;
        getline(cin, num_input);
        string char_input;
        getline(cin, char_input);

        vector<string>num_vec = handleInput(num_input);
        vector<string>char_vec = handleInput(char_input);

        vector<pair<int, char>>card_v;
        int v_size = num_vec.size();
        for (int i=0; i<v_size; i++)
        {
            int num = stoi(num_vec[i]);
            char ch = char_vec[i][0];
            card_v.push_back(make_pair(num, ch));
        }
        Solution03 solu(card_v);

        return 0;
	}
	{
        vector<pair<string, string>>card_v;
        for (int i=0; i<5; i++)
        {
            pair<string, string>p_item;
            cin >> p_item.first >> p_item.second;
            card_v.push_back(p_item);
        }

        Solution02 solu(card_v);

        return 0;
	}
/*
4
3 2 6 3
0 1 1 0
2
*/
    int v_size;
    cin >> v_size;

    vector<int>weight_v(v_size);
    for (int i=0; i<v_size; i++)
    {
        cin >> weight_v[i];
    }

    vector<int>kind_v(v_size);
    for (int i=0; i<v_size; i++)
    {
        cin >> kind_v[i];
    }

    int K;
    cin >> K;

    Solution01 solu(weight_v, kind_v, K);
    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
